package com.linwen.excise.leetcode;


/**
 * 相应的，爬楼梯问题也可简化成顺序求解的问题，只用计算后续两个的和
 * @author : linwen
 * @date : 12:14 下午 2020/11/1
 */
public class _1137第n个斐波那契数 {
    public static void main(String[] args) {
        int n = 4;
        System.out.println(tribonacci(n));
    }

    private static int tribonacci(int n) {
        if(n==0) {return 0;}
        if(n==1) {return 1;}
        if(n==2) {return 1;}
        //return tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3); 可能超时
        int sum = 0;
        int x=0,y=1,z=1;
        for (int i = 3; i <=n ; i++) {
            sum = x+y+z;
            x=y;
            y=z;
            z=sum;
        }
        return z;
    }
}
